/**
 * @file ParentTree.c
 * @desc 使用「双亲表示法」实现树的存储结构与基本操作，包括初始化、创建样例树、查找节点及获取双亲节点等功能。
 * @author WangBlue (wangjiping596@gmail.com)
 * @date 2025/10/17 9:24
 * @version 1.0
 */

#include <stdio.h>
#define MAX_SIZE 100  // 树中最多节点数

/**
 * @struct PNode
 * @brief 树节点结构（双亲表示法）
 *
 * @var data 节点存储的数据（字符类型）
 * @var parentIdx 双亲节点在数组中的下标（根节点的 parentIdx = -1）
 */
typedef struct PNode {
    char data;
    int parentIdx;
} PNode;

/**
 * @struct PTree
 * @brief 双亲表示法存储的树结构
 *
 * @var nodes 以数组形式存放所有节点
 * @var amount 当前树中节点的数量
 */
typedef struct PTree {
    PNode nodes[MAX_SIZE];
    int amount;
} PTree;

/**
 * @brief 初始化树结构
 * @param tree 指向待初始化树结构的指针
 *
 * @note
 * 初始化后，树为空树（amount = 0）。
 */
void initTree(PTree* tree) {
    tree->amount = 0;
}

/**
 * @brief 构建一个示例树（硬编码方式）
 *
 * 树的逻辑结构如下：
 * ```
 *        A
 *      / | \
 *     B  C  D
 *        / \
 *       E   F
 * ```
 * 其中：
 * - A 为根节点；
 * - B、C、D 的双亲为 A；
 * - E、F 的双亲为 C。
 *
 * @param tree 指向待创建的树结构
 */
void createSampleTree(PTree* tree) {
    initTree(tree);
    tree->amount = 6;

    // 初始化节点数据及其双亲下标
    tree->nodes[0] = (PNode){'A', -1};  // 根节点
    tree->nodes[1] = (PNode){'B', 0};   // B 的双亲是 A (索引 0)
    tree->nodes[2] = (PNode){'C', 0};   // C 的双亲是 A
    tree->nodes[3] = (PNode){'D', 0};   // D 的双亲是 A
    tree->nodes[4] = (PNode){'E', 2};   // E 的双亲是 C (索引 2)
    tree->nodes[5] = (PNode){'F', 2};   // F 的双亲是 C
}

/**
 * @brief 查找指定字符对应的节点
 * @param tree 指向树结构的指针
 * @param str  要查找的节点字符
 * @return 若找到则返回节点指针；若树为空或节点不存在，返回 NULL
 */
PNode* findNode(PTree* tree, char str) {
    if (tree->amount == 0) return NULL;  // 空树判断

    for (int i = 0; i < tree->amount; i++) {
        if (tree->nodes[i].data == str) {
            return &tree->nodes[i];  // 找到节点，返回指针
        }
    }
    return NULL;  // 未找到
}

/**
 * @brief 获取指定节点的双亲节点
 * @param tree 指向树结构的指针
 * @param str  待查询的节点字符
 * @return 若找到双亲节点，返回其指针；若无双亲（根节点）或未找到节点，返回 NULL
 *
 * @note
 * - 根节点（parentIdx = -1）没有双亲；
 * - 本函数依赖 findNode() 查找节点。
 */
PNode* getParent(PTree* tree, char str) {
    if (tree->amount == 0) return NULL;  // 空树
    PNode* node = findNode(tree, str);   // 查找指定节点
    if (node == NULL) return NULL;       // 未找到节点

    if (node->parentIdx == -1) return NULL; // 根节点无双亲

    return &tree->nodes[node->parentIdx];   // 返回双亲节点指针
}

/**
 * @brief 主函数：测试双亲表示法的树结构
 */
int main() {
    PTree tree;

    // 构建示例树
    createSampleTree(&tree);

    // 查找节点 'E' 的双亲
    PNode* parentNode = getParent(&tree, 'E');
    if (parentNode != NULL)
        printf("Parent of E: %c\n", parentNode->data);
    else
        printf("E has no parent or not found.\n");

    return 0;
}
